package main.java.easy;

import java.util.HashMap;

/**
 * @Author: 郑国荣
 * @Date: 2023-06-30-21:57
 * @Description: 给定一个整数数组 nums和一个整数目标值 target，请你在该数组中找出 和为目标值 target的那两个整数，并返回它们的数组下标。
 */
public class TwoSum {
    /**
     * 时间复杂度：O(N^2)
     * 空间复杂度：O（1）
     */
        public static int[] twoSum(int[] nums, int target) {
            int[] result = new int[2];
            for(int i =0;i<nums.length-1;i++){
                for(int j=i+1;j<nums.length;j++){
                    if(nums[i]+nums[j]==target){
                        result[0]=i;
                        result[1]=j;
                        return result;
                    }
                }
            }
            return null;
        }
    /**
     * 时间复杂度：O(N)
     * 空间复杂度：O（N）
     */
        public static int[] twoSum_2(int[] nums,int target){
            HashMap<Integer,Integer> hashMap = new HashMap<>();
            for (int i = 0; i < nums.length; i++) {
                if (hashMap.containsKey(target-nums[i])){
                    return new int[]{hashMap.get(target-nums[i]),i};
                }
                hashMap.put(nums[i],i);
            }
            return null;
        }




        public static void main(String[] args) {
            int[] nums = {2, 1,1,1,1,1,8,15,3};
            int target = 18;
            int[] result = twoSum_2(nums, target);
//            int[] result = twoSum(nums, target);
            if(result == null) {
                System.out.println("未找到符合要求的数对");
            } else {
                System.out.println("符合要求的数对为：" + result[0] + "，" + result[1]);
            }
        }


}
